/*
题目：合并k个升序链表
给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。
https://leetcode.cn/problems/merge-k-sorted-lists/submissions/
 */
public class MergeKLists {
    public ListNode mergeKLists(ListNode[] lists) {
        //由于成员是链表，所以需要定义它的比较器
        PriorityQueue<ListNode> heap = new PriorityQueue<> (new ListCmp());
        ListNode dummy = new ListNode();//傀儡节点
        ListNode ret = dummy;

        //初步构造小根堆
        for (ListNode node : lists) {
            if (node != null) {
                heap.offer(node);
            }
        }

        while (!heap.isEmpty()) {
            ListNode tmp = heap.poll();
            dummy.next = tmp;
            tmp = tmp.next;
            dummy = dummy.next;
            if (tmp != null) {
                heap.offer(tmp);
            }
        }
        dummy.next = null;

        return ret.next;
    }
}
class ListCmp implements Comparator<ListNode> {

    public int compare(ListNode o1, ListNode o2) {
        return o1.val - o2.val;
    }
}
